67. 生成哈夫曼树

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function(line) {
    rl.on('line', function(line) {
        const values = line.split(' ').map(Number);
        const root = buildHuffmanTree(values);
        const res = [...traverse(root, [])].join(' ');
        console.log(res);
    });
});

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class MinQueue {
    constructor() {
        this.elements = [];
    }

    enqueue(element) {
        this.elements.push(element);
        this.elements.sort((a, b) => a.value - b.value);
    }

    dequeue() {
        return this.elements.shift();
    }

    isEmpty() {
        return this.elements.length === 0;
    }
}

function buildHuffmanTree(values) {
    const pq = new MinQueue();
    values.forEach(v => pq.enqueue(new Node(value)));

    while(pq.elements.length > 1) {
        const left = pq.dequeue();
        const right = pq.dequeue();
        const parent = new Node(left.value + right.value);
        parent.left = left;
        parent.right = right;
        pq.enqueue(parent);
    }

    return pq.dequeue();
}

function traverse(root, arr) {
    if (root) {
        traverse(root.left);
        arr.push(root.value);
        traverse(root.right);
    }
}